home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / sortseq.h < prev    next >
C/C++ Source or Header  |  1994-08-05  |  7KB  |  185 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  sortseq.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_SORTSEQ_H
  17. #define LEDA_SORTSEQ_H
  18.  
  19. /*
  20. #include <LEDA/impl/rs_tree.h>
  21. #define SEQ_DEF_IMPL rs_tree
  22. #define SEQ_BASE_IMPL bin_tree
  23. typedef rs_tree_item seq_item;
  24. */
  25.  
  26. #include <LEDA/impl/skiplist.h>
  27. #define SEQ_DEF_IMPL skiplist
  28. #define SEQ_BASE_IMPL skiplist
  29. typedef skiplist_item seq_item;
  30.  
  31.  
  32. template<class ktype, class itype>
  33.  
  34. class _CLASSTYPE sortseq : public virtual SEQ_DEF_IMPL {
  35.  
  36. int  int_type()              const { return INT_TYPE(ktype); }
  37. int  cmp(GenPtr x, GenPtr y) const
  38.                      { return compare(ACCESS(ktype,x),ACCESS(ktype,y)); }
  39. void clear_key(GenPtr& x)   const { Clear(ACCESS(ktype,x)); }
  40. void clear_inf(GenPtr& x)   const { Clear(ACCESS(itype,x)); }
  41. void copy_key(GenPtr& x)    const { x = Copy(ACCESS(ktype,x)); }
  42. void copy_inf(GenPtr& x)    const { x = Copy(ACCESS(itype,x)); }
  43. void print_key(GenPtr x)    const { Print(ACCESS(ktype,x),cout); }
  44. void print_inf(GenPtr x)    const { Print(ACCESS(itype,x),cout); }
  45.  
  46. public:
  47.  
  48. virtual ktype  key(seq_item it) const { return ACCESS(ktype,SEQ_DEF_IMPL::key(it)); }
  49. virtual itype  inf(seq_item it) const { return ACCESS(itype,SEQ_DEF_IMPL::inf(it)); } 
  50.  
  51. virtual seq_item lookup(ktype y) const { return SEQ_DEF_IMPL::lookup(Convert(y)); }
  52. virtual seq_item locate(ktype y) const { return SEQ_DEF_IMPL::locate(Convert(y)); }
  53. virtual seq_item locate_succ(ktype y) const { return SEQ_DEF_IMPL::locate_succ(Convert(y)); }
  54. virtual seq_item locate_pred(ktype y) const { return SEQ_DEF_IMPL::locate_pred(Convert(y)); }
  55.  
  56. virtual seq_item min() const { return SEQ_DEF_IMPL::min(); }
  57. virtual seq_item max() const { return SEQ_DEF_IMPL::max(); }
  58.  
  59. virtual seq_item succ(seq_item x) const { return SEQ_DEF_IMPL::succ(x); }
  60. virtual seq_item succ(ktype y) const { return locate_succ(y); }
  61.  
  62. virtual seq_item pred(seq_item x) const { return SEQ_DEF_IMPL::pred(x); }
  63. virtual seq_item pred(ktype y) const { return locate_pred(y); }
  64.  
  65. virtual seq_item insert(ktype y,itype x)
  66.                          { return SEQ_DEF_IMPL::insert(Convert(y),Convert(x)); } 
  67.  
  68. virtual seq_item insert_at(seq_item it,ktype y,itype x)
  69. { return SEQ_DEF_IMPL::insert_at_item(it,Convert(y),Convert(x)); } 
  70.  
  71. virtual int      size()  const { return SEQ_DEF_IMPL::size(); }
  72.  
  73. virtual bool     empty() const { return (size()==0) ? true : false; }
  74.  
  75. virtual void     clear() { SEQ_DEF_IMPL::clear(); }
  76.  
  77. virtual void reverse_items(seq_item a, seq_item b) { SEQ_DEF_IMPL::reverse_items(a,b); }
  78. virtual void flip_items(seq_item a, seq_item b)    { reverse_items(a,b); }
  79.  
  80. virtual void del(ktype y)         { SEQ_DEF_IMPL::del(Convert(y)); } 
  81. virtual void del_item(seq_item it)  { SEQ_DEF_IMPL::del_item(it); } 
  82. virtual void change_inf(seq_item it, itype i) { SEQ_DEF_IMPL::change_inf(it,Convert(i));}
  83. virtual void split(seq_item x,sortseq<ktype,itype>& S1,sortseq<ktype,itype>& S2)
  84.                       { SEQ_DEF_IMPL::split_at_item(x,(SEQ_DEF_IMPL&)S1,(SEQ_DEF_IMPL&)S2); }
  85.  
  86. virtual sortseq<ktype,itype>& conc(sortseq<ktype,itype>& S) { SEQ_DEF_IMPL::conc((SEQ_DEF_IMPL&)S); return *this; }
  87.  
  88. sortseq()    {}
  89. sortseq(const sortseq<ktype,itype>& w) : SEQ_BASE_IMPL(w) {}
  90.  
  91. sortseq<ktype,itype>& operator=(const sortseq<ktype,itype>& w)
  92. { SEQ_DEF_IMPL::operator=(w); return *this; }
  93.  
  94. virtual ~sortseq()   { clear(); }
  95. };
  96.  
  97.  
  98.  
  99. //------------------------------------------------------------------------------
  100. //
  101. // Sorted sequences with implementation parameter:
  102. //
  103. //   _sortseq<ktype,itype,seq_impl> 
  104. //
  105. //------------------------------------------------------------------------------
  106.  
  107. #define _sortseq_class(ktype,itype,impl)\
  108. \
  109. class _CLASSTYPE _sortseq_class_(ktype,itype,impl) : private virtual impl, public sortseq<ktype,itype>\
  110. {\
  111. int int_type() const { return INT_TYPE(ktype); }\
  112. \
  113. int cmp(GenPtr x, GenPtr y) const\
  114. { return compare(ACCESS(ktype,x),ACCESS(ktype,y)); }\
  115. void clear_key(GenPtr& x) const { Clear(ACCESS(ktype,x)); }\
  116. void clear_inf(GenPtr& x) const { Clear(ACCESS(itype,x)); }\
  117. void copy_key(GenPtr& x) const { x = Copy(ACCESS(ktype,x)); }\
  118. void copy_inf(GenPtr& x) const { x = Copy(ACCESS(itype,x)); }\
  119. void print_key(GenPtr x) const { Print(ACCESS(ktype,x),cout); }\
  120. void print_inf(GenPtr x) const { Print(ACCESS(itype,x),cout); }\
  121. \
  122. public:\
  123. \
  124. ktype key(seq_item it) const { return ACCESS(ktype,impl::key(impl::item(it))); }\
  125. itype inf(seq_item it) const { return ACCESS(itype,impl::inf(impl::item(it))); }\
  126. \
  127. seq_item lookup(ktype y) const { return (seq_item)impl::lookup(Convert(y)); }\
  128. seq_item locate(ktype y) const { return (seq_item)impl::locate(Convert(y)); }\
  129. seq_item locate_succ(ktype y) const { return (seq_item)impl::locate_succ(Convert(y)); }\
  130. seq_item locate_pred(ktype y) const { return (seq_item)impl::locate_pred(Convert(y)); }\
  131. \
  132. seq_item min() const { return (seq_item)impl::min(); }\
  133. seq_item max() const { return (seq_item)impl::max(); }\
  134. \
  135. seq_item succ(seq_item x) const { return (seq_item)impl::succ(impl::item(x)); }\
  136. seq_item succ(ktype y) const { return locate_succ(y); }\
  137. \
  138. seq_item pred(seq_item x) const { return (seq_item)impl::pred(impl::item(x)); }\
  139. seq_item pred(ktype y) const { return locate_pred(y); }\
  140. \
  141. seq_item insert(ktype y,itype x)\
  142. { return (seq_item)impl::insert(Convert(y),Convert(x));}\
  143. \
  144. seq_item insert_at(seq_item it,ktype y,itype x)\
  145. { return (seq_item)impl::insert_at_item(impl::item(it),Convert(y),Convert(x));}\
  146. void reverse_items(seq_item a, seq_item b) { impl::reverse_items(impl::item(a),impl::item(b)); }\
  147. void flip_items(seq_item a, seq_item b) { reverse_items(a,b); }\
  148. \
  149. void del(ktype y) { impl::del(Convert(y)); }\
  150. void del_item(seq_item it) { impl::del_item(impl::item(it)); }\
  151. void change_inf(seq_item it, itype i) { impl::change_inf(impl::item(it),Convert(i));}\
  152. \
  153. int      size()  const { return impl::size(); }\
  154. bool     empty() const { return (size()==0) ? true : false; }\
  155. void     clear() { impl::clear(); }\
  156. \
  157. void split(seq_item it,sortseq<ktype,itype>& S1,sortseq<ktype,itype>& S2)\
  158. { impl::split_at_item(impl::item(it),*(impl*)&S1,*(impl*)&S2); }\
  159. \
  160. sortseq<ktype,itype>& conc(sortseq<ktype,itype>& S)\
  161. { impl::conc(*(impl*)&S); return *this; }\
  162. \
  163. _sortseq_class_(ktype,itype,impl)() {}\
  164. _sortseq_class_(ktype,itype,impl)(const _sortseq_(ktype,itype,impl)& S) : impl(S) {}\
  165. \
  166. _sortseq_(ktype,itype,impl)& operator=(const _sortseq_(ktype,itype,impl)& S)\
  167. { impl::operator=(S); return *this; }\
  168. \
  169. ~_sortseq_class_(ktype,itype,impl)() { impl::clear(); }
  170.  
  171. #if defined(__TEMPLATE_ARGS_AS_BASE__)
  172. #define _sortseq_class_(a,b,c) _sortseq
  173. #define _sortseq_(a,b,c) _sortseq<a,b,c>
  174. template <class ktype, class itype, class impl> 
  175. _sortseq_class(ktype,itype,impl)
  176. };
  177. #else
  178. #define _sortseq(a,b,c)         name4(a,b,c,_sortseq)
  179. #define _sortseq_class_(a,b,c)  name4(a,b,c,_sortseq)
  180. #define _sortseq_(a,b,c)        name4(a,b,c,_sortseq)
  181. #define _sortseqdeclare3(_a,_b,_c) _sortseq_class(_a,_b,_c) };
  182. #endif
  183.  
  184. #endif
  185.